Skip to main content

3-3 680.验证回文字符串 Ⅱ

Date：2022-03-06 20:01:10

标签：

  • 双指针
  • 贪心

附题：

  • 验证回文串

题目：680.验证回文字符串 Ⅱ ( 简单😄 )​

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例​

示例1

输入: "aba"

输出: True

示例2

输入: "abca"

输出: True

解释: 你可以删除 c 字符。

分析​

  • 暴力法：首先验证原串是否为回文串，如果是则返回True，否则，枚举每一个位置空缺时候，是否为回文串。

    时间O(N^2)，空间O(1)

  • 贪心法：依旧利用双指针，如果当前两个指针指向值相同，那么继续下一步，如果不相同，则认为(左指针+1)和右指针指向相同 或者 左指针和(右指针+1)指向相同，否则返回False

    时间O(N)，空间O(1)

附：贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

题解​

暴力法

function validPalindrome(s: string): boolean {
  const len = s.length
  let i = 0
  let j = len - 1
  let res = true

  while (i < j) {
    if (s[i] != s[j]) {
      res = false
      break
    }

    ++i
      --j
  }

  if (res) {
    console.log('[删除位置]:', '无需删除')
    return true
  }

  for (let k = 0; k < len; ++k) {
    i = 0
    j = len - 1
    res = true

    while (i <= j) {
      if (i == k) ++i
      if (j == k) --j

      if (s[i] != s[j]) {
        res = false
        break
      }

      ++i
        --j
    }

    if (res) {
      console.log('[删除位置]:', k)
      return true
    }
  }

  return false
}

贪心法

function validPalindrome111(s: string): boolean {
  const len = s.length
  let low = 0
  let high = len - 1

  while (low < high) {
    if (s[low] == s[high]) {
      ++low;
      --high
    } else {
      return validPalindromeAssist(s, low + 1, high) || validPalindromeAssist(s, low, high - 1)
    }
  }

  return true


  function validPalindromeAssist(s: string, low: number, high: number): boolean {
    let i = low
    let j = high
    while (i < j) {
      if (s[i] != s[j]) {
        return false
      }

      ++i;
      --j
    }

    return true
  }
}

基础题1：验证回文串 ( 简单😄 )​

给定一个非空字符串 s，判断是否能成为回文字符串。

解法有：

  • 反转序列法：将字符串反转，如果与原串相等，则认为true

    时间O(N)，空间O(N)，空间是因为需要通过额外的数组去转化（即字符串转数组，数组再转字符串）

  • 双指针法：定义两个指针，分别指向头和尾，并分别向中间必进，其过程中，如果不相等，则认为false (O(N))

    时间O(N)，空间O(1)

双指针法

function validPalindrome(s: string): boolean {
  const len = s.length
  let i = 0
  let j = len - 1
  let res = true

  while (i < j) {
    if (s[i] != s[j]) {
      res = false
      break
    }

    ++i;
      --j
  }

  return res
}

基础题2：反转数组​

给定一个数组，将其元素反转

示例：

输入 arr: [1,2,3,4]

输出 arr: [4,3,2,1]

分析

  • 额外数组法：声明一个数组，从后向前写入即可
  • 双指针法：定义两个指针 i 和 j ，分别指向头和尾，两头逼近中间，分别交换，直至 i==j